/*
 * @lc app=leetcode.cn id=239 lang=typescript
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start

//  思路：优先队列
//  参考：https://labuladong.github.io/algo/2/18/44/

// 复杂度：O(n) O(n)

function maxSlidingWindow(nums: number[], k: number): number[] {
    const window = new MonotonicQueue()
    const res = []
    for (let i = 0; i < nums.length; i++) {
        if (i < k - 1) {
            //先填满窗口的前 k - 1
            window.push(nums[i])
        } else {
            // 窗口向前滑动，加入新数字
            window.push(nums[i])
            // 记录当前窗口的最大值
            res.push(window.max())
            // 移出旧数字
            window.pop(nums[i - k + 1])
        }
    }
    return res
};

class MonotonicQueue {
    q: number[]
    constructor() {
        this.q = []
    }
    push(n: number) {
        // 将小于 n 的元素全部删除
        while (this.q.length && this.q[this.q.length - 1] < n) {
            this.q.pop()
        }
        // 然后将 n 加入尾部
        this.q.push(n)
    }
    max(): number {
        return this.q[0]
    }
    pop(n: number) {
        if (n === this.q[0]) {
            this.q.shift()
        }
    }
}
// @lc code=end

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))
